package 回溯;

import com.google.common.collect.Lists;

import java.util.*;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @createTime 2023年03月02日 19:08:00
 */
public class 串联字符串的最大长度1239 {
	public static void main(String[] args) {
		System.out.println(maxLength(Lists.newArrayList("uu")));
		int i=0;
		System.out.println(i++);
	}

	static int max = 0;

	public static int maxLength(List<String> arr) {
		if (arr.isEmpty()) {
			return 0;
		}
		//先排序，减少重复
		Collections.sort(arr);
		backTrace(arr, arr.size(), 0);
		return max;
	}

	static LinkedList<String> temp = new LinkedList<>();
	static Set<Character> usedChar = new HashSet<>();

	public static void backTrace(List<String> arr, int length, int cur) {
		//到了最后，结束循环
		if (length == cur) {
			return;
		}
		//遍历可选项
		outer:
		for (int i = cur; i < length; i++) {
			//检查第一个字母
			char[] tempCharArr = arr.get(i).toCharArray();
			if (isFilter(tempCharArr)){
				//做选择
				temp.add(arr.get(i));
				for (char c : tempCharArr) {
					usedChar.add(c);
				}
				int len = 0;
				for (String s : temp) {
					len += s.length();
				}
				max = Math.max(max, len);
				backTrace(arr, length, i + 1);
				temp.removeLast();
				for (char c : tempCharArr) {
					usedChar.remove(c);
				}
			}
		}
	}

	public static boolean isFilter(char[] tempCharArr) {
		Set<Character> tempChar = new HashSet<>();
		//检查是否有重复的
		for (char c : tempCharArr) {
			if (usedChar.contains(c)) {
				return false;
			}
			if (tempChar.contains(c)) {
				return false;
			}
			tempChar.add(c);
		}
		return true;
	}
}
